perm filename DES.2[NBS,WD] blob
sn#357577 filedate 1976-04-17 generic text, type T, neo UTF8
DATA ENCRYPTION ALGORITHM
Introduction
The algorithm is designed to encipher and decipher blocks of data
consisting of 64 bits under control of a 64 bit key. Deciphering must be
accomplished by using the same key as for enciphering, but with the schedule of
addressing the key bits altered so that the deciphering process is the reverse
of the enciphering process. A block to be enciphered is subjected to an
initial permutation IP, then to a complex key-dependent computation and finally
to a permutation which is the inverse of the initial permutation IP↑-1. The
key-dependent computation can be simply defined in terms of a function f, called
the cipher function, and a function KS, called the key schedule. A description
of the computation is given first, along with details as to how the algroithm is
used for encipherment. Next, the use of the algorithm for decipherment is
described. Finally, a definition of the cipher function f is given in terms of
primitive functions which are called the selection functions Si and the
permutation function. Si, P and KS of the algorithm are contained in the
Appendix.
The following notation is convenient: Given two blocks L and R of
bits, LR denotes the block consisting of the bits of L followed by the bits of
R. Since concatentation is associative B1B2...B8, for example, denotes the
block consisting of the bits of B1 followed by the bits of B2... followed by the
bits of B8.
Enciphering
A sketch of the enciphering computation is given in Figure 1.
The 64 bits of the input block to be enciphered are first subjected to
the following permutation, called the initial permutation IP:
IP
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
That is the permuted input has bit 58 of the input as its first bit, bit
50 as its second bit, and so on with bit 7 as its last bit. The permuted input
block is then the input to a complex key-dependent computation described below.
The output of that computation, called the preoutput, is then subjected to the
following permutation which is the inverse of the initial permutation:
-1
IP
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
1
ENCIPHERING COMPUTATION
---------------------------------------------
| INPUT |
---------------------------------------------
↓
--------------------------
( INITIAL PERMUTATION )
--------------------------
|
-----------------o-----------------
↓ ↓
PERMUTED --------------------------- ---------------------------
INPUT | L0 | | R0 |
--------------------------- ---------------------------
| _________________|_________________K1
↓ ↓ |
(+)←-------------(f)---------------o
|________________ ________________|
_________________X_________________
↓ ↓
--------------------------- ---------------------------
| L1 = R0 | | R1 = L0(+)f(R0,K1) |
--------------------------- ---------------------------
| _________________|_________________K2
↓ ↓ |
(+)←-------------(f)---------------o
|________________ ________________|
_________________X_________________
↓ ↓
--------------------------- ---------------------------
| L2 = R1 | | R2 = L1(+)f(R1,K2) |
--------------------------- ---------------------------
| _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _Kn
↓ ↓ |
(+)←- - - - - - -(f)← - - - - - - -o
|_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|
_ _ _ _ _ _ _ _ X _ _ _ _ _ _ _ _
↓ ↓
--------------------------- ---------------------------
| L15 = R14 | | R15 = L14(+)f(R14,K15) |
--------------------------- ---------------------------
| _________________|_________________K16
↓ ↓ |
(+)←-------------(f)---------------o
↓ ↓
--------------------------- ---------------------------
PREOUTPUT | R16 = L15(+)f(R15,K16) | | L16 = R15 |
--------------------------- ---------------------------
| |
-----------------o-----------------
↓
--------------------------
( INVERSE INITIAL PERM )
--------------------------
↓
---------------------------------------------
| OUTPUT |
---------------------------------------------
Figure 1
2
That is, the output of the algorithm has bit 40 of the preoutput block
as its first bit, bit 8 as its second bit, and so on, until bit 25 of the
preoutput block is the last bit of the output.
The computation which uses the permuted input block as its input to
produce the preoutput block consists, but for a final interchange of blocks, of
16 iterations of a calculation that is described below in terms of the cipher
function f which operates on two blocks, one of 32 bits and one of 48 bits, and
produces a block of 32 bits.
Let the 64 bits of the input block to an iteration consist of a 32 bit
block L followed by a 32 bit block R. Using the notation defined in the
introduction, the input block is then LR.
Let K be a block of 48 bits chosen from the 64 bit key. Then the output
L'R' of an interation with input LR is defined by:
(1) L' = R
R' = L + f(R,K)
where + denotes bit-by-bit addition modulo 2.
As remarked before, the input of the first iteration of the calculation
is the permuted input block. If L'R' is the output of the 16th iteration then
R'L' is the preoutput block. At each iteration a different block K of key bits
is chosen from the 64 bit key designated by KEY.
With more notation we can describe the iterations of the computation in
more detail. Let KS be a function which takes an integer n in the range from 1
to 16 and a 64 bit block KEY as input and yields as output a 48 bit block Kn
which is a permuted selection of bits from KEY. That is
(2) Kn = KS(n,KEY)
with Kn determined by the bits in 48 distinct bit positions of KEY. KS is called
the key schedule because the block K used in the n'th iteration of (1) is the
block Kn determined by (2).
As before, let the permuted input block be LR. Finally, let Lo and Ro
be respectively L and R and let Ln and Rn be respectively L' and R' of (1) when
L and R are respectively Ln-1 and Rn-1 and K is Kn; that is,when n is in the
range from 1 to 16,
(3) Ln = Rn-1
Rn = Ln-1 + f(Rn-1,Kn)
The preoutput block is then R16L16.
The key schedule KS of the algorithm is described in detail in the
Appendix. The key schedule produces the 16 Kn which are required for the
algorithm.
Deciphering
The permutation IP↑-1 applied to the preoutput block is the inverse of
the initial permutation IP applied to the input. Further, from (1) it follows
that:
(4) R = L'
L = R' + f(L',K)
3
Consequently, to decipher it is only necessary to apply the very same
algorithm to an enciphered message block, taking care that at each iteration of
the computation the same block of key bits K is used during decipherment as was
used during the incipherment of the block. Using the notation of the previous
section, this can be expressed by the equations:
(5) Rn-1 = Ln
Ln-1 H Rn + f(ln,Kn)
where now L16R16 is the premuted input block for the deciphering calculation and
L1R1 is the preoutput block. That is, for the decipherment calculation with
R16L16 as the permuted input, K16 is used in the first iteration, K15 in the
second, and so on, with K1 used in the 16th iteration.
The Cipher Function f
A sketch of the calculation of f(R,K) is given in Figure 2.
CALCULATION OF f(R,K)
-------------------------
| R (32 bits) |
-------------------------
|
↓
-
( E )
-
|
↓
--------------------------------- ---------------------------------
| 48 bits | | K (48 bits) |
--------------------------------- ---------------------------------
| |
| |
| - |
--------------------→( + )←-------------------
-
|
↓
----------------------------------------------------------------------------
|||||| |||||| |||||| |||||| |||||| |||||| |||||| ||||||
------ ------ ------ ------ ------ ------ ------ ------
( S1 ) ( S2 ) ( S3 ) ( S4 ) ( S5 ) ( S6 ) ( S7 ) ( S8 )
------ ------ ------ ------ ------ ------ ------ ------
|||| |||| |||| |||| |||| |||| |||| ||||
|||| |||| |||| |||| |||| |||| |||| ||||
--------------------------------------------------------------------------
|
↓
-
( P )
-
|
↓
-------------------------
| 32 bits |
-------------------------
Figure 2
4
Let E denote a function which takes a block of 32 bits as input and
yields a block of 48 bits as output. Let E be such that the 48 bits of its
output, written as 8 blocks of 6 bits each, are obtained by selecting the bits
in its inputs in order according to the following table:
E BIT-SELECTION TABLE
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
Thus the first three bits of E(R) are the bits in positions 32, 1 and 2
of R while the last 2 bits of E(R) are the bits in positions 32 and 1.
Each of the unique selection functions S1, S2, ..., S8, takes a 6 bit
block as input and yields a 4 bit block as output and is illustratted by using a
table containing the recommended S1:
S1
Column Number
Row |
No. | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
|________________________________________________________________
|
0 | 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 | 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 | 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 | 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
If S1 is the function defined in this table and B is a block of 6 bits, then
S1(B) is determined as follows: The first and last bits of B represent in base
2 a number in the range 0 to 3. Let that number be i. The middle 4 bits of B
represent in base 2 a number in the range 0 to 15. Let that number be j. Look
up in the table the number in the i'th row and j'th column. It is a number in
the range 0 to 15. and is uniquely represented by a 4 bit block. That block is
the output S1(B) of S1 for the input B. For example, the input 011011 the row
is 01, that is row 1, and the column is determined by 1101, that is column 13.
In row 1 column 13 appears 5 so that the output is 0101. Selection functions
S1, S2,...,S8 of the algorithm appear in the Appendix.
The permutation function P yields a 32 bit output from a 32 bit input by
permuting the bits of the input block. Such a function is defined by the
following table:
P
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
5
The output P(L) for the function P defined by this table is obtained
from the input L by taking the 16th bit of L as the first bit of P(L), the 7th
bit as the second bit of P(L), and so on until the 25th bit of L is taken as the
32nd bit of P(L). The permutation function P of the algorithm is repeated in
the Appendix.
Now let S1,...,S8 be eight distinct selection functions, let P be the
permutation function and let E be the function defined above.
To define f(R,K) we first define B1,...,B8 to be blocks of 6 bits each for which
(6) B1B2...B8 = K + E(R)
The block f(R,K) is then defined to be
(7) P(S1(B1)S2(B2)...S8(B8))
Thus K + E(R) is first divided into the 8 blocks as indicated in (6).
Then each Bi is taken as an input to Si and the 8 blocks S1(B1),S2(B2),...S8(B8)
of 4 bits each are consolidated into a single block of 32 bits which forms the
input to P. The output (7) is then the output of the function f for the inputs R
and K.
6
APPENDIX
PRIMITIVE FUNCTIONS FOR THE
DATA ENCRYPTION ALGORITHM
The choice of the primitive functions KS, S1, ..., S8 and P is critical
to the strength of an encipherment reulting from the algorithm. Specified below
is the recommended set of functions, describing S1, ..., S8 and P in the same
way they are described in the algorithm. For the interpretation of the tables
describing these functions, see the discussion in the body of the algorithm.
The primitive functions S1,...,S8, are:
S1
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S2
15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
S3
10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
S4
7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
S5
2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
S6
12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
A1
S7
4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
S8
13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
The primitive function P is:
P
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
Recall that Kn, for 1≤n≤16, is the block of 48 bits in (2) of the
algorithm. Hence, to describe KS, it is sufficient to describe the calculation
of Kn from KEY for n=1, 2, ..., 16. That calculation is illustrated in Figure
3. To complete the definition of KS it is therefore sufficient to describe the
two permuted choices, as well as the schedule fo left shifts. One bit in each
eight-bit byte of the KEY may be utilized for error detection in key generation,
distribution and storage. Bits 8, 16, ..., 64 are for use in assuring that each
byte is of odd parity.
Permuted choice 1 is determined by the following table:
PC-1
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
The table has been divided into two parts, with the first part
determining how the bits of C0 are chosen, and the second part determining how
the bits of D0 are chosen. The bist of KEY are numbered 1 through 64. The
bist of C0 are respectively bits 57, 49, 41, ..., 44 and 36 of KEY, with the
bits of D0 being bits 63, 55, 47, ..., 12 and 4 of KEY.
A2
KEY SCHEDULE CALCULATION
---------------------------------------------
| KEY |
---------------------------------------------
|
↓
---------------
( PERMUTED )
( CHOICE 1 )
---------------
|
↓
---------------------------
↓ ↓
-------------------- --------------------
| C0 | | D0 |
-------------------- --------------------
↓ ↓
----------- -----------
( LEFT ) ( LEFT )
( SHIFT ) ( SHIFT )
----------- -----------
↓ ↓
-------------------- --------------------
| C1 | | D1 |
-------------------- --------------------
| ↓ ------------
|-------------------------------------→( PERMUTED )--→ K1
↓ ↓ ( CHOICE 2 )
----------- ----------- ------------
( LEFT ) ( LEFT )
( SHIFTS ) ( SHIFTS )
----------- -----------
↓ ↓
-------------------- --------------------
| Cn | | Dn |
-------------------- --------------------
| ↓ ------------
|-------------------------------------→( PERMUTED )--→ Kn
↓ ↓ ( CHOICE 2 )
----------- ----------- ------------
( LEFT ) ( LEFT )
( SHIFTS ) ( SHIFTS )
----------- -----------
↓ ↓
-------------------- --------------------
| C16 | | D16 |
-------------------- --------------------
| ↓ ------------
|-------------------------------------→( PERMUTED )--→ K16
( CHOICE 2 )
------------
Figure 3
A3
With C0 and D0 defined, we how define how the blocks Cn and Dn are
obtained from the blocks Cn-1 and Dn-1, respectively, for n = 1, 2, ..., 16.
That is accomplished by adhering to the following schedule of left shifts of the
individual blocks:
Iteration Number of
Number Left Shifts
1 1
2 1
3 2
4 2
5 2
6 2
7 2
8 2
9 1
10 2
11 2
12 2
13 2
14 2
15 2
16 1
For example, C3 and D3 are obtained from C2 and D2, respectively, by two
left shifts, and C16 and D16 are obtained from C15 and D15, respectively, by one
left shift. In all cases, by a single left shift is meant a rotation of the
bits one place to the left, so that after one left shift the bits in the 28
positions are the bits that were previously in positions 2, 3, ..., 28, 1.
Permuted choice 2 is determined by the following table:
PC-2
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Therefore, the first bit of Kn is the 14th bit of CnDn, the second bit
the 17th, and so on with the 47th bit the 29th, and the 48th bit the 32nd.
A4